//class Solution {
//public:
//    string tree2str(TreeNode* root) {
//        string ret;
//        if (root == nullptr) return ret;
//        ret += to_string(root->val);
//        if (root->left != nullptr)
//        {
//            ret += '(';
//            ret += tree2str(root->left);
//            ret += ')';
//        }
//        if (root->right != nullptr)
//        {
//            if (root->left == nullptr) ret += "()";
//            ret += '(';
//            ret += tree2str(root->right);
//            ret += ')';
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr) return ret;
//        queue<TreeNode*> q; q.push(root);
//        while (q.size())
//        {
//            vector<int> v;
//            int levelsize = q.size();
//            while (levelsize--)
//            {
//                TreeNode* Node = q.front(); q.pop(); v.push_back(Node->val);
//                if (Node->left) q.push(Node->left);
//                if (Node->right) q.push(Node->right);
//            }
//            ret.push_back(v);
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    vector<vector<int>> levelOrderBottom(TreeNode* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr) return ret;
//        queue<TreeNode*> q; q.push(root);
//        while (q.size())
//        {
//            int sz = q.size();
//            vector<int> v;
//            while (sz--)
//            {
//                TreeNode* node = q.front(); q.pop();
//                v.push_back(node->val);
//                if (node->left) q.push(node->left);
//                if (node->right) q.push(node->right);
//            }
//            ret.push_back(v);
//        }
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};




//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//        stack<TreeNode*> q; TreeNode* node = root;
//        while (q.size() || node)
//        {
//            while (node)
//            {
//                ret.push_back(node->val);
//                q.push(node);
//                node = node->left;
//            }
//            node = q.top();
//            q.pop();
//            node = node->right;
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        stack<TreeNode*> st;
//        TreeNode* node = root;
//        while (st.size() || node)
//        {
//            while (node)
//            {
//                st.push(node);
//                node = node->left;
//            }
//            node = st.top(); st.pop();
//            ret.push_back(node->val);
//            node = node->right;
//        }
//        return ret;
//    }
//};





class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        if (root == nullptr)
            return v;

        stack<TreeNode*> st;
        TreeNode* cur = root, * prev = nullptr;
        while (cur)
        {
            st.push(cur);
            if (cur->left)
                cur = cur->left;
            else
                break;
        }

        while (!st.empty())
        {
            cur = st.top();
            if (cur->right == prev || cur->right == nullptr)
            {
                v.push_back(cur->val);
                prev = cur;
                st.pop();
            }
            else
            {
                cur = cur->right;
                while (cur)
                {
                    st.push(cur);
                    cur = cur->left;
                }
            }
        }
        return v;
    }
};